package JZ;

public class jz7重构二叉树 {
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    public static void main(String[] args) {
        TreeNode t = reConstructBinaryTree(new int[]{1,2,4,7,3,5,6,8}, new int[]{4,7,2,1,5,3,8,6});
        System.out.println(t.val);
    }
    public static TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        return backtrack(0, pre.length, pre, 0, vin.length, vin);
    }
    public static TreeNode backtrack(int p_l, int p_r, int[] pre, int v_l, int v_r, int[] vin){
        if(p_r - p_l == 1 && v_r - v_l == 1)
            return new TreeNode(pre[p_l]);
        if(p_r - p_l < 1 || v_r - v_l < 1)
            return null;
        TreeNode node = new TreeNode(pre[p_l]);
        int i = -1;
        for (i = v_l; i < v_r; i++) {
            if(vin[i] == pre[p_l])
                break;
        }
        node.left = backtrack(p_l + 1, p_l + 1 + i - v_l, pre, v_l, i, vin);
        node.right = backtrack(p_l + 1 + i - v_l, p_r, pre, i + 1, v_r, vin);
        return node;
    }

}
